package org.pupil.search.binarySearch;

import org.pupil.search.ISearch;

import java.util.Arrays;

/**
 * @Description: 二分搜索：找峰值元素，二分搜索法不只应用于有序数组
 * 峰值元素是指其严格大于左右相邻值的元素
 * 给你一个整数数组 nums，已知任何两个相邻的值都不相等
 * 找到峰值元素并返回其索引
 * 数组可能包含多个峰值，在这种情况下，返回 任何一个峰值 所在位置即可。
 * 可以假设 nums[-1] = nums[n] = 无穷小
 * 必须实现时间复杂度为 O(log n) 的算法来解决此问题。
 * @Author: pupil
 * @Date: 2024/08/01 下午 4:07
 */
public class FindPeakElement {

    public static void main(String[] args) {
        // 数据数组最大长度
        int N = 1000;
        // 随机数组每个值，在1~V之间随机
        int V = 1000;
        // 测试次数
        int testNumber = 500;
        System.out.println("测试开始");

        for (int i = 0; i < testNumber; i++) {
            int n = (int) (Math.random() * N);
            int[] arr = ISearch.randomArray(n, V);
            int ans = findPeakElement(arr);
            if (ans == -1) {
                System.out.println("出错了！");
            }
        }
        System.out.println("测试结束");
    }

    /**
     * 找峰值元素
     *
     * @param arr 数组
     * @return
     */
    public static int findPeakElement(int[] arr) {
        int n = arr.length;

        // 单独判断数组中只有一个元素的情况
        // 小     小
        // -1  0  1
        if (arr.length == 1) {
            return 0;
        }

        // 数组长度为2的情况
        // 单独验证0位置，是不是峰值
        if (arr[0] > arr[1]) {
            return 0;
        }

        // 单独验证n-1位置，是不是峰值
        if (arr[n - 1] > arr[n - 2]) {
            return n - 1;
        }

        // X     中间一定有峰值点    X
        // 0      1 ~ n-2         n-1
        // 中间：1 ~ n-2，一定有峰值点
        int l = 1, r = n - 2, m = 0, ans = -1;
        while (l <= r) {
            m = l + ((r - l) >> 1);
            if (arr[m] < arr[m - 1]) {
                // 中间值小于左侧, 下降趋势，则缩小右边范围，往左继续二分
                r = m - 1;
            } else if (arr[m] < arr[m + 1]) {
                // 中间值小于右侧, 上降趋势，则缩小左边范围，往右继续二分
                l = m + 1;
            }else {
                // 找到峰值，记录答案直接返回
                ans = m;
                break;
            }
        }
        return ans;
    }
}
